package bfs;

import java.util.LinkedList;

public class HuaWei {


    public  int find(int[][] grid){

        int len1 = grid.length;
        int len2 = grid[0].length;
        LinkedList<int[]> queue = new LinkedList<>();
        int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}};
//TODO:2023/11/1
//        boolean[][] used = new boolean[m][n];
//        used[i][0] = true;
        int ans=100010;
        for (int i = 0; i <len1 ; i++) {
            if (grid[i][0]==1){
                queue.add(new int[]{0,i,0});
                while (!queue.isEmpty()){
                    int[] cur = queue.pollFirst();
                    int d=cur[0];
                    int x=cur[1];
                    int y=cur[2];
                    if (y==len2-1){
                        ans=Math.min(ans,d);
                    }
                    for (int [] next:
                         dirs) {
                        int nextX=x+next[0];
                        int nextY=y+next[1];
                        if (nextX>=0&&nextX<len1&&nextY>=0&&nextY<len2){
                            queue.add(new int[]{d+1,nextX,nextY});
                        }
                        //TODO:2023/11/1             if (nx < 0 || ny < 0 || nx >= m || ny >= n || used[nx][ny] || grid[nx][ny] != 1) continue;
                        //                            used[nx][ny] = true;
                        //                            dq.add(new int[]{d+1, nx,ny});
                    }
                }
            }
        }
        return  ans;


    }
}
